package solution;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2021-09-30 16:41
 */
public class Solution_11backtrack {
    /*===========================================================================================================================
     *回溯 46. 全排列
     * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
     *  */
    List<List<Integer>> res46;
    /*
    * 路径是path
    * 选择列表是nums
    * 结束条件：当nums中的元素都在path中时。
    */
    void backtrack46(int[] nums,LinkedList<Integer> path){
        System.out.println(path.size()+","+nums.length);
        if(path.size()==nums.length){
            res46.add(new LinkedList<>(path));
            System.out.println(path);
            return;
        }
        for (int n:nums) {
            //每个数子只能在path中出现一次
            if (path.contains(n))continue;
            //做选择
            path.add(n);
            //递归进入下一层决策
            backtrack46(nums,path);
            //取消选择
            path.removeLast();
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        res46=new LinkedList<>();
        //路径
        LinkedList<Integer> path=new LinkedList<>();
        backtrack46(nums,path);
        return res46;
    }

    /*===========================================================================================================================
     *回溯 78. 子集
     * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
     * 1.数学归纳法
     * 2.回溯
     *  */
    //1.数学归纳法：如果 A = subset([1,2]) ，那么：subset([1,2,3])= A + [A[i].add(3) for i = 1..len(A)]
    public List<List<Integer>> subsets1(int[] nums) {
        if (nums.length==0){
            List<Integer> ans=new LinkedList<>();
            List<List<Integer>> res=new LinkedList<>();
            res.add(ans);
            return res;
        }
        // 把最后一个元素拿出来
        int lestnum=nums[nums.length-1];
        //截取出去掉最后一个元素后的数组
        int[] subNums=new int[nums.length-1];
        for (int i = 0; i < subNums.length; i++) {
            subNums[i]=nums[i];
        }
        // 先递归算出前面元素的所有子集
        List<List<Integer>> res=subsets1(subNums);
        int size=res.size();
        for (int i = 0; i < size; i++) {
            //在每个子集追加最后的元素，然后将结果放入集合中
            List<Integer> resi=res.get(i);
            List<Integer> addList=new LinkedList<>(resi);
            addList.add(lestnum);
            res.add(addList);
        }
        return res;
    }

    List<List<Integer>> res78;
    //2.回溯
    public List<List<Integer>> subsets(int[] nums) {
        res78=new LinkedList<>();
        LinkedList<Integer> path=new LinkedList<>();
        backtrack78(nums,0,path);
        return res78;
    }
    /*
     * 路径：path记录已选择过的数组元素
     * 选择列表：nums中从index之后的元素可以选择加入path中
     * 终止条件：由于是子集，所有没有base case，每一步都需要将当前路径加入到结果集合中
     */
    void backtrack78(int[] nums,int index,LinkedList<Integer> path){
        res78.add(new LinkedList<>(path));
        for (int i = index; i < nums.length; i++) {
            // 做选择
            path.add(nums[i]);
            //回溯计算下一个选择
            backtrack78(nums,i+1,path);
            //取消选择
            path.removeLast();
        }
    }

    /*===========================================================================================================================
     *回溯 77. 组合
     * 输入两个数字 n, k，算法输出 [1..n] 中 k 个数字的所有组合。按照组合的定义，[1,2] 和 [2,1] 也算重复
     * 回溯：典型的回溯算法，k 限制了树的高度，n 限制了树的宽度
     *  */
    List<List<Integer>> res77;
    public List<List<Integer>> combine(int n, int k) {
        res77=new LinkedList<>();
        LinkedList<Integer> path=new LinkedList<>();
        backtrack77(n,k,1,path);
        return res77;
    }
    /*
     * 路径：path记录已选择过的元素
     * 选择列表：从index之后到n的数字可以选择加入path中
     * 终止条件：当path中的元素个数达到k个
     */
    void backtrack77(int n,int k,int index,LinkedList<Integer> path){
        //base case
        if (path.size()==k){
            res77.add(new LinkedList<>(path));
        }
        for (int i = index; i <=n; i++) {
            //做选择
            path.add(i);
            //递归调用下一选择
            backtrack77(n,k,i+1,path);
            path.removeLast();
        }
    }



    /*===========================================================================================================================
     *回溯 51. N 皇后
     *  */
    List<List<String>> res51=new LinkedList<>();
    int size;
    /*
    * 路径：board中前row-1行成功放置的皇后位置
    * 选择列表：第row行的所以位置
    * 结束条件：row超过board的最后一行
    */
    void backtrack51(LinkedList<String> board,int row){
        //判断结束条件
        if (row==size){
            res51.add(new LinkedList<>(board));
            return;
        }
        int n=size;
        for (int c = 0; c < n; c++) {
            if (!chack(board,row,c)){
                continue;
            }
            //做选择
            String rows="";
            for (int i = 0; i <n; i++) {
                if (i==c)
                    rows+="Q";
                else
                    rows+=".";
            }
            board.add(rows);
            //递归下一决策
            backtrack51(board,row+1);
            //撤销选择
           board.removeLast();
        }
    }
    //用于检查在第row行的col位置是否合法
    boolean chack(LinkedList<String> board,int row,int col){
        int rowSize=board.size();
        System.out.println(rowSize);
        // 检查列是否有皇后互相冲突
        for (int i = 0; i < rowSize; i++) {
            if (board.get(i).charAt(col)=='Q')
                return false;
        }
        // 检查右上方是否有皇后互相冲突
        for (int i = row-1,j=col+1; i >= 0 && j<size; i--,j++) {
            if (board.get(i).charAt(j)=='Q')
                return false;
        }
        // 检查左上方是否有皇后互相冲突
        for (int i = row-1,j=col-1; i >= 0&&j>=0; i--,j--) {
            if (board.get(i).charAt(j)=='Q')
                return false;
        }
        return true;
    }
    public List<List<String>> solveNQueens(int n) {
        size=n;
        //初始化棋盘为nxn
        List<String> board=new LinkedList<>();
        backtrack51((LinkedList<String>) board,0);
        return res51;
    }

    /*===========================================================================================================================
     *回溯 37. 解数独
     * 每行，每列，各个3*3的宫内不能有重复
     *  */
    public void solveSudoku(char[][] board) {
        backtrack37(board,0,0);
    }
    /*
    * 路径：对board[i][j]前的位置选择过的
    * 选择列表：1-9中的不违反规则的元素
    * 终止条件：到达棋盘的最后
    */
    // 对 board[i][j] 进行穷举尝试
    boolean backtrack37(char[][] board, int i, int j) {
        int n=9,m=9;
        if (j==m){
            // 穷举到最后一列的话就换到下一行重新开始。
            return backtrack37(board,i+1,0);
        }
        if (i==n){
            //base case 找到一个可行解
            return true;
        }
        if (board[i][j]!='.'){
            //当前位置是预设值
            return backtrack37(board,i,j+1);
        }
        for (char k = '1'; k <='9' ; k++) {
            if (!chack37(board,i,j,k)){
                continue;
            }
            //作出选择
            board[i][j]=k;
            if (backtrack37(board,i,j+1))
                // 如果找到一个可行解，立即结束
                return true;
            //撤销选择
            board[i][j]='.';
        }
        return false;
    }
    boolean chack37(char[][] board,int row,int col,char ch){
        for (int i = 0; i < 9; i++) {
            if (board[row][i]==ch){
                return false;
            }
            if (board[i][col]==ch)
                return false;
            if (board[(row/3)*3+i/3][col/3*3+i%3]==ch)
                return false;
        }
        return true;
    }


    /*===========================================================================================================================
     *回溯  22. 括号生成
     * 请你写一个算法，输入是一个正整数 n，输出是 n 对儿括号的所有合法组合，
     * 1、一个「合法」括号组合的左括号数量一定等于右括号数量，这个很好理解。
     * 2、对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量。
     *  */
    List<String> res22;
    public List<String> generateParenthesis(int n) {
        res22=new LinkedList<>();
        if (n==0){
            String s="";
            res22.add(s);
            return res22;
        }
        StringBuffer path=new StringBuffer();
        backtrack22(n,n,n,path);
        return res22;
    }
    /*
    * 路径：path记录的
    * 选择列表：左括号或者右括号
    * 结束条件：左右括号的个数都刚好使用n个
    */
    // 可用的左括号数量为 left 个，可用的右括号数量为 rgiht 个
    void backtrack22(int left, int right, int n, StringBuffer path){
        // 若左括号剩下的多，说明不合法
        if (right<left)
            return;
        // 数量小于 0 肯定是不合法的
        if (left<0||right<0){
            return;
        }
        // 当所有括号都恰好用完时，得到一个合法的括号组合
        if (left==0&&right==0){
            res22.add(path.toString());
            return;
        }
        // 尝试放一个左括号
        path.append('(');
        backtrack22(left-1,right,n,path);
        path.deleteCharAt(path.length()-1);
        // 尝试放一个右括号
        path.append(')');
        backtrack22(left,right-1,n,path);
        path.deleteCharAt(path.length()-1);
    }

    /*===========================================================================================================================
     *回溯 698. 划分为k个相等的子集
     * 视角一，如果我们切换到这 n 个数字的视角，每个数字都要选择进入到 k 个桶中的某一个。
     * 视角二，如果我们切换到这 k 个桶的视角，对于每个桶，都要遍历 nums 中的 n 个数字，然后选择是否将当前遍历到的数字装进自己这个桶里。
     *  */
    //1.以数字的视角：递归暴力求解
    public boolean canPartitionKSubsets1(int[] nums, int k) {
        //当数组元素不够k个是一定不可能平均分的
        if(k>nums.length)return false;
        int sum=0;
        for (int n:nums) {
            sum+=n;
        }
        //当数组元素的和不能平均分配到k份时，直接返回
        if (sum%k!=0) return false;
        // k 个桶（集合），记录每个桶装的数字之和
        int[] bucket=new int[k];
        int target=sum/k;

        //如果我们提前对 nums 数组排序，然后从后向前遍历，把大的数字排在前面，那么大的数字会先被分配到 bucket 中，对于之后的数字，
        //bucket[i] + nums[index] 会更大，更容易触发剪枝的 if 条件。
        Arrays.sort(nums);
        return backtrack698(nums,nums.length-1,bucket,target);
    }
    //递归，判断 nums 是否能划分成 k 个和为 target 的子集
    boolean backtrack698(int[] nums,int index,int[] bucket,int target){
        if (index==-1){
            //判断是否每个桶的和都是target
            for (int b:bucket) {
                if (b!=target)
                    return false;
            }
            return true;
        }

        // 穷举 nums[index] 可能装入的桶
        for (int i = 0; i < bucket.length; i++) {
            // 剪枝，桶装装满了
            if (bucket[i]+nums[index]>target)continue;
            //作出选择
            bucket[i]=bucket[i]+nums[index];
            if (backtrack698(nums,index-1,bucket,target))
                return true;
            //撤销选择
            bucket[i]-=nums[index];
        }
        //index装入哪个桶都不行
        return false;
    }

    //2.以桶的视角：对每个桶需要思考nums中的所有数字，判断每个数字是否要放入桶中
    public boolean canPartitionKSubsets(int[] nums, int k) {
        //当数组元素不够k个是一定不可能平均分的
        if (k > nums.length) return false;
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }
        //当数组元素的和不能平均分配到k份时，直接返回
        if (sum % k != 0) return false;
        int target = sum / k;
        boolean[] visited=new boolean[nums.length];
        return backtrack698_1(k,0,nums,0,visited,target);
    }
    //backtrack698_1表示对于第k个桶，当前桶中元素和为bucket，对nums[index]元素是否可以加入，visited标记以及加入到桶中的元素，target表示每个桶中的目标和
    boolean backtrack698_1(int k,int bucket,int[] nums,int index,boolean[] visited,int target){
        if (k==0){
            //表示k个桶以及都装好了
            // 所有桶都被装满了，而且 nums 一定全部用完了
            // 因为 target == sum / k
            return true;
        }
        if (bucket==target){
            // 装满了当前桶，递归穷举下一个桶的选择
            // 让下一个桶从 nums[0] 开始选数字
            return backtrack698_1(k-1,0,nums,0,visited,target);
        }

        // 从 index 开始向后探查有效的 nums[i] 装入当前桶
        for (int i = index; i < nums.length; i++) {
            if (visited[i])
                continue;
            if (bucket+nums[i]>target)
                continue;
            // 做选择，将 nums[i] 装入当前桶中
            visited[i]=true;
            bucket+=nums[i];
            // 递归穷举下一个数字是否装入当前桶
            if (backtrack698_1(k,bucket,nums,index+1,visited,target)){
                return true;
            }
            //取消选择
            visited[i]=false;
            bucket-=nums[i];
        }
        return false;
    }

    /*===========================================================================================================================
     *回溯 494. 目标和
     *  */
    int res494;
    public int findTargetSumWays(int[] nums, int target) {
        if (nums.length==0)
            return 0;
        backtrack494(nums,0,target);
        return res494;
    }
    /*
    * 路径：nums中index之前的元素都已经选择的符号序列，和为target-rest
    * 选择列表：对于每个index位置的元素可以选择+或者-
    * 终止条件：当nums中的每个元素都有了符号，且和刚好等于target时，找到一个路径
    * */
    void backtrack494(int[] nums,int index,int rest){
        //base case
        if (index==nums.length){
            if (rest==0) res494++;
            return;
        }

        // 给 nums[index] 选择 - 号
        rest+=nums[index];
        backtrack494(nums,index+1,rest);
        rest-=nums[index];

        //给 nums[index] 选择 + 号
        rest-=nums[index];
        backtrack494(nums,index+1,rest);
        rest+=nums[index];
    }

    public static void main(String[] args) {
        Solution_11backtrack obj=new Solution_11backtrack();
        int[] nums=new int[]{1,2,3};
        List<List<Integer>> lists = obj.permute(nums);
        for (List<Integer> l:lists) {
            System.out.println(l);
        }
    }

}
